package 字典树;

import java.util.Arrays;

/**
 * Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。
 * 这一数据结构有相当多的应用情景，例如自动补完和拼写检查
 * https://leetcode.cn/problems/implement-trie-prefix-tree/
 * search()查询是否存在字符串
 * startsWith()查询是否存在前缀
 *
 */
public class Solution {

    class Trie {
        final int N = 100009;
        int[][] trie = new int[N][26];
        int[] count = new int[N];
        int index = 0;
        public Trie() {}
        public void insert(String word) {
            int p = 0;
            for(int i = 0; i < word.length(); i++){
                int u = word.charAt(i) - 'a';
                if (trie[p][u] == 0) trie[p][u] = ++index;
                p = trie[p][u];
            }
            count[p]++;
        }

        public boolean search(String word) {
            int p = 0;
            for(int i = 0; i< word.length(); i++){
                int u = word.charAt(i) - 'a';
                if (trie[p][u] == 0) return false;
                p = trie[p][u];
            }
            return count[p] != 0;
        }

        public boolean startsWith(String prefix) {
            int p = 0;
            for(int i = 0; i< prefix.length(); i++){
                int u = prefix.charAt(i) - 'a';
                if (trie[p][u] == 0) return false;
                p = trie[p][u];
            }
            return true;
        }
    }
}
